package org.example.Greedy_Algorithm;

import java.util.ArrayList;
import java.util.Arrays;

public class petrol_station {
    public static void main(String[] args) {
        //加油站

        //在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
        //你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
        //给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
        int[] gas = {5, 5, 1, 3, 4};
        int[] cost = {8, 1, 7, 1, 1};
        int i = canCompleteCircuit(gas, cost);
        System.out.println(i);
    }

    public static int canCompleteCircuit2(int[] gas, int[] cost) {
        if (gas.length == 1 && gas[0] >= cost[0]) return 0;
        if (getSum(cost) > getSum(gas)) return -1;
        int index = -1;
        int fuelTank = -1;
        for (int i = 0; i < gas.length; i++) {
            if (gas[i] <= cost[i]) continue;
            int len = gas.length;
            index = i;
            fuelTank = gas[index];
            while (len > 0) {
                if (fuelTank < 0) break;
                if (fuelTank - cost[index] < 0) {
                    fuelTank = -1;
                    break;
                }
                if (index != gas.length - 1) {
                    fuelTank += gas[index + 1] - cost[index];
                    index++;
                } else {
                    fuelTank += gas[0] - cost[index];
                    index = 0;
                }
                len--;
            }
            if (fuelTank >= 0) break;
        }
        return fuelTank < 0 ? -1 : index;
    }

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas.length == 1 && gas[0] >= cost[0]) return 0;
        if (getSum(cost) > getSum(gas)) return -1;
        int index = -1;
        int[] nums = new int[gas.length];
        Arrays.fill(nums, -1);
        for (int i = 0; i < gas.length; i++) {
            if (gas[i] <= cost[i]) continue;
            nums[i] = i;
        }
        Arrays.sort(nums);
        int fuelTank = -1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == -1) break;
            int len = gas.length;
            index = nums[i];
            fuelTank = gas[index];
            while (len > 0) {
                if (fuelTank < 0) break;
                if (fuelTank - cost[index] < 0) {
                    fuelTank = -1;
                    break;
                }
                if (index != gas.length - 1) {
                    fuelTank += gas[index + 1] - cost[index];
                    index++;
                } else {
                    fuelTank += gas[0] - cost[index];
                    index = 0;
                }
                len--;
            }
            if (fuelTank >= 0) break;
        }

        return fuelTank < 0 ? -1 : index;
    }

    public static int getSum(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
}
